package com.learn.algorlthm;

/**
 * @classname:
 * @Description:从1到n整数中1出现的次数
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-08-08 13:56
 */
public class Learn43 {

    /**
     * 具体解题思路请自行百度，这里描述不清
     */
    public static int numberOf1Between1AndN_Solution(int n) {
        int cnt = 0;

        for (int m = 1; m <= n; m *= 10) {
            int a = n/m, b = n%m;

            /* 情况一: 个位数值大于1 (a/10+1)*m      (2到9)
             * 情况二: 个位数值等于1 (a/10)*m + (b+1)
             * 情况三: 个位数值等于0 (a/10)*m
             * 综上所述
             */
            cnt+= (a + 8)/10*m + (a%10 == 1 ? (b+1) : 0);
        }

        return cnt;
    }
}
